/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum = function (candidates, target) {
  if (candidates.length === 0) {
    return []
  }
  candidates.sort((a, b) => b - a);
  let result = []
  if (candidates[0] === target) {
    result.push([target])
  } else if (candidates[0] < target) {
    result.push(...combinationSum(candidates, target - candidates[0])
      .map(item => [candidates[0], ...item]))
  }
  result.push(...combinationSum(candidates.slice(1), target));
  return result;
};
// @lc code=end